Euler Problem 76

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?



In [1]:

    
# Generate pentagonal numbers
# p(k) = k * (3k-1) / 2, k not zero.

def pentagonal(N):
    a, b = 1, 2
    delta = 4
    sgn = 1
    while a <= N:
        yield sgn, a
        a += delta
        if b <= N:
            yield sgn, b
            b += delta + 1
        delta += 3
        sgn = -sgn
        
N = 100
partitions = [0] * (N+1)
partitions[0] = 1
for n in range(1, N+1):
    for sgn, g in pentagonal(n):
        partitions[n] += sgn  * partitions[n - g]
print(partitions[N])

190569292

Explanation: Uses the pentagonal number recurrence for the partition counting function.

http://en.wikipedia.org/wiki/Pentagonal_number_theorem#Partition_recurrence